package leetcode

type ListNode struct {
	Val  int
	Next *ListNode
}

func partition(head *ListNode, x int) *ListNode {
	head1, head2 := ListNode{0, nil}, ListNode{0, nil}
	tailPtr1, tailPtr2 := &head1, &head2
	for p := head; p != nil; p = p.Next {
		if p.Val < x {
			tailPtr1.Next = p
			tailPtr1 = tailPtr1.Next
		} else {
			tailPtr2.Next = p
			tailPtr2 = tailPtr2.Next
		}
	}
	tailPtr1.Next = head2.Next
	tailPtr2.Next = nil
	return head1.Next
}
